@Order Fulfillment Cycle Time Estimation for On-Demand Food Delivery
[[Abstract]]
送达时间 Order Fulfillment Cycle Time (OFCT)
a novel post-processing layer
- accounting for the distributional mismatch between the true OFCT values and those predicted by the model at initialization
By providing customers with conveniences such as easy access to an extensive variety of restaurants, effortless food ordering and fast delivery, on-demand food delivery (OFD) platforms have achieved explosive growth in recent years. A crucial machine learning task performed at OFD platforms is prediction of the Order Fulfillment Cycle Time (OFCT), which refers to the amount of time elapsed between a customer places an order and he/she receives the meal. The accuracy of predicted OFCT is important for customer satisfaction, as it needs to be communicated to a customer before he/she places the order, and is considered as a service promise that should be fulfilled as well as possible. As a result, the estimated OFCT also heavily influences planning decisions such as dispatching and routing.
[[Attachments]]
相关工作
ETA 分类
Route-based
OD-based
OFCT 比其他 ETA 独特的挑战
Significantly more influencing factors
location and characteristics of the restaurant
the food preparation time
the orders assigned to the same courier (which will alter his/her delivery itinerary) 骑手配送行为
Unavailability of critical information 预估时缺少关键信息
分配到订单的骑手
最终的路线
Time Window Assignment Problem
BackGroound
城市划分成区域，区域内配送站
- 订单终点对应一个指定的 poi 类型(学校、写字楼等)
订单生命周期划分 PT(下单到取到餐)，DT(取餐到送达)，OFCT(下单到送达)，CT(下单到做好)
流程
用户下单时，预估 OFCT
dispatching 分单
routing 路径规划
- VRPTW
骑手到达餐厅取餐
骑手配送
Feature
订单特征
Spartial feature 空间特征
- 起点终点 id 和坐标，city/grid id
Temporal feature 时间特征
hour of the day
workday
Order size features 订单大小影响商家出餐速度
sku_num
price
- sku_num 低估套餐的大小
Aggregation Features 聚合特征
通过手机传感器收集信息(gps，wifi，bluetooth)，得到 dt/pt/ofct
对上面的信息进行聚合：20 分位数、平均、标准差、80 分位数
通过一定规则选取订单集合，在集合中再分组计算统计信息。
相同 city/grid/restaurant/hour of day 的订单
发单前不同时长完成订单
Dish Features 餐品特征
sku 分配 uid，订单可以用包含的 uid 表示
训练分类模型( 116 类)，使用预测的分类结果
sku 标题做为输入，人工标签
fine-tuning 中文 Bert
Cooking Time Features
出餐时间很难获取真值，从历史数据中挖掘。
三种场景
骑手到达太早，需要等到出餐完成
骑手需要在同一个餐厅取多个订单，只有在餐厅完成最后一个订单才能离开
骑手达到时，如果餐厅完成出餐可以立即进行配送统计
聚合 departure time from the restaurant 得到 ct
Supply-and-Demand Features 供需特征
供需比 demand-to-supply ratio (DSR) $\mathrm{DSR}{o}=|C|^{-1}\left|O{o}^{\text {uncompleted }}\right|$
订餐需求在时间和空间上都会有突变，此时通过合并订单配送策略减轻影响。合单策略提升整体配送效率，但是单个订单配送时间变长(骑手需要绕路去取或送)。通过 DSR 来描述这种现象
$O_{o}^{\text {uncompleted }}$ 当前未完成订单，DSR 表示当前未完成订单和活跃配送员数的比例
配送比 dropoff_ratio $o_{o}=\left|O_{o}^{\text {uncompleted }}\right|^{-1}\left|O_{o}^{\text {dropoff }}\right|$
- 未完成订单中，已经取餐在配送中的订单占比
餐厅出餐量 unfetched_order_count
- 骑手未取订单数，值越大需要等待的时间越大
单量预测相关，尝试后发现没用
- 单量预测模型中使用的特征 OFCT 预估模型也使用，没有带来新的信息增益。
图例
e DSR 越大，Bundle 越大，g 对应 OCFT 变大
DSR 一定，dropoff ratio 越大，代表快要释放的运力更多，然后bundle变小，ocft 变小。
Courier Features 骑手特征
预测 OFCT 时，送单的骑手还没有确定，通过预测模型对附近的骑手进行排序，取 top-ranked 骑手做为派单对象。
相关特征
取单距离
work load 负载，骑手当前未完成订单数
urgency 紧急程度，骑手需要配送订单平均或最小剩余时间
Mutual Distances 订单终点、餐厅、骑手当前订单的终点的最短距离。距离越大，骑手越有可能绕路。
ETA-based Drop-off Time Feature 多维度相似订单的配送 ETA
利用回归模型来学习配送段 ETA 无法很好处理长尾不规律 case，比如高峰期等待电梯
利用历史订单作为配送段时间预估的语料
历史订单用多维特征来表示
新订单通过 k 近邻搜索出相似的历史订单
对相似的历史订单真实配送段时间加权平均，作为新订单的预估配送段时间
通过 OD-based ETA 方法(TEMP+R) 预估餐厅到终点的配送时间特征 DTo
$\mathbf{x}{\widetilde{o}}^{\text {eta }}=\left[\operatorname{lon}\left(r{\widetilde{o}}\right) \text {, lat }\left(r_{\widetilde{o}}\right), \operatorname{lon}\left(p_{\widetilde{o}}\right) \text {, lat }\left(p_{\widetilde{o}}\right), \operatorname{hr}\left(a_{\widetilde{\sigma}}^{\text {creation }}\right)\right]^{T} \odot w$
- 用经纬度+时间组成的向量表示订单，w 表示向量中每一项的权重
$\operatorname{dissim}(\widetilde{o}, \widehat{o})=\left|\mathbf{x}{\widetilde{o}}^{\text {eta }}-x{\widehat{o}}^{\text {eta }}\right|_{2}$
- 用 Euclidean distance 表示两个不同订单之间的距离
$\left(\sum_{i=1}^{k} w_{i}\right)^{-1} \sum_{i=1}^{k}\left(w_{i} \cdot \mathrm{DT}{o{i}}\right)$
在历史订单中取 k 个最相似订单，构建该特征
$w_{i}=\exp \left(-\frac{\operatorname{dissim}\left(o_{i}, o\right)}{\sigma^{2}}\right)$ 代表权重
Meteorological Features 气象
数值特征
气温
空气质量
风速
类别特征
- 天气
Model
- 网络结构
-
数值特征 归一化+ ELU 升维
- 维度太低限制神经网络表达
类别特征 embedding + dropout 避免过拟合
- 一个类别多个id 对应 embedding 进行 average pooling
骑手特征
召回 pickup 距离在 X 米范围内的骑手组成骑手集合
re-ranking module
Query Invariant Listwise Context Modeling (QILCM)对于每个骑手 c 生成表示向量 hc 以及排序分 sc，利用加权得分表示骑手向量
- $\sum_{\forall c \in C^{\text {candidate }}} s_{c} \tilde{\mathbf{h}}_{c}$
Postprocessing 后处理
模型收敛速度慢，预测效果差
- 模型拟合的数据分布与真实履约时间的分布发生偏移，真实的履约时间实际上是一个右偏长尾的分布，相当于有一小部分订单真实的配送时间偏长而模型没有学习到。
$\mathrm{OFCT}_o^{\text {predict }}=\mu^{\text {real }}+\sigma^{\text {real }} \frac{y_o^{\text {out }}-\mu^{\text {ini }}}{\sigma^{\text {ini }}}$
实现拟合和缩放
y_out 是模型输出
real 是根据真实数据统计的均值和方差
ini 是整个训练集的均值和方差
自适应 [[Box-Cox Transformation]] 逆变换
- 更加能够拟合长尾数据分布
Objective Function
$\ell_{\text {predict }}+\lambda \ell_{\text {rank }}$
- ranking loss + predictive loss
$\ell_{\text {predict }}=\left|\mathrm{OFCT}_o^{\text {predict }}-\mathrm{OFCT}_o\right|$
$\ell_{\text {rank }}=-\sum_{\forall c \in C^{\text {candidate }}}\left(\mathbb{I}\left(c=c_o\right) \log \left(s_c\right)\right)$
cross entropy loss
$\mathbb{I}()$ 是指示函数
Experiments
Ablation Analysis of Feature Groups 消融实验
- 订单特征、供需特征
不同模型对比
GBM
[[DeepFM]] [[@xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systems]]
- 简单 concatenation&MLP 策略，不适合 OFCT 任务
[[TEMP+R]] [[MURAT]] OD-based ETA methods
Conclusion
可以改进的点
cooking time features
weather prediction
Ref
@Order Fulfillment Cycle Time Estimation for On-Demand Food Delivery